package com.ftg.learn.chapter01;

/**
 * 快慢指针问题
 *
 * @author 布衣
 */
public class Linked {

    /**
     * 成员内部类
     */
    private class Node {
        int val;
        Node next;

        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    //连表  ： 第一个节点  ： 头节点
    private Node head;
    //双指针
    private Node tail;
    //中间元素
    private Node middle;
    //中间索引
    private int middleVal;

    private int size;

    //add(4)  add(3)  add(5)  N +1
    public void addTail(int val) {
        if (null == head) {
            head = new Node(val, null);
            tail = head;
            middle = head;
            middleVal = 0;
            size++;
            return;
        }
        tail.next = new Node(val, null);
        tail = tail.next;
        if(++size % 2 ==0){
            middle = middle.next;
            middleVal++;
        }
    }

    /**
     * 0
     *
     * @param index
     */
    public void deleteByIndex(int index) {
        //移位 以 删除问题
        //昨界问题 ：
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("索引不能小于0");
        }

        //思路 ： 快慢指针  head=0  middleVal = n/2[middle]   tail = n-1;

        //index = 3;  tail = 8;   共9个   下标 middleValue= 4;
        if(index < middleVal){
            Node cur = head;
            int n = 0;
            while(cur.next != null){
                n++;
                if(n==index){
                    cur.next = cur.next.next;
                }
                cur = cur.next;
            }
        }

    }

    public static void main(String[] args) {
        Linked linked = new Linked();
        linked.addTail(1);
        linked.addTail(2);
        linked.addTail(3);
        linked.addTail(4);
        linked.addTail(5);
        linked.addTail(6);
        System.out.println();

    }

}
